package 力扣日常刷题.木22二月.第17天223;

/**
 * @author 帅小伙
 * @date 2022/2/23
 * @description
 */
public class Demo139将数组分成和相等的三个部分 {

    public boolean canThreePartsEqualSum(int[] arr) {
        int n = arr.length;
        int[] sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + arr[i];
        }
        if(sum[n] % 3 != 0) return false;
        int t = sum[n]/3;
        int i = 0,j = 0;

        // 前缀和 ＋  判断
        for (i = 1; i <= n - 2; i++) {
            if(sum[i] != t) continue;
            for ( j = i+1; j <= n - 1; j++) {
                if(sum[n] - sum[j]== t){
                    return true;
                }
            }
        }
        return false;
    }

}
